package cn.xkai.exercise.a;

/**
 * @description: 翻转字符串里的单词
 * 时间复杂度O(n)
 * 自己的思路：
 * 普通版：空间复杂度O(n) - 去除前后空格，然后以空格分组，倒序循环输出，中间涉及的空格跳过
 * 进阶版：空间复杂度O(1) - 未完成
 * 借鉴的思路：双向链表 - 从后往前寻找单词，遇到空格，则重新寻找单词，然后把找到的单词进行重新拼接到尾部
 * @author: kaixiang
 * @date: 2022-06-24
 **/
public class Solution10 {
    public String reverseWords(String s) {
        String[] words = s.trim().split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = words.length - 1; i >= 0; i--) {
            if (words[i].length() == 0) {
                continue;
            }
            sb.append(words[i]).append(" ");
        }
        return sb.toString().trim();
    }

    public String reverseWordsRefer(String s) {
        s = s.trim();
        int len = s.length();
        // 单词起止坐标
        int begin = len, end = len;
        while (--len >= 0) {
            // 遇到非单词分隔的空格符的情况
            if (s.charAt(len) == ' ' && begin == end) {
                s = s.substring(0, len) + s.substring(len + 1);
                begin--;
                end--;
            } else if (s.charAt(len) == ' ' && begin != end) {
                String word = s.substring(begin, end);
                s = s.substring(0, len) + (end < s.length() ? s.substring(end) : "") + word + " ";
                begin--;
                end = begin;
            } else if (len == 0) {
                String word = s.substring(0, end);
                s = s.substring(0, len) + (end < s.length() ? s.substring(end) : "") + word;
            } else {
                begin--;
            }
        }
        return s;
    }

    public static void main(String[] args) {
        String s = "the sky is blue";
        Solution10 solution10 = new Solution10();
        System.out.println(solution10.reverseWords(s));
    }
}
